package day07;

// 练习 day07
// 三角形最小路径和
// 先找每个位置的最小路径和，再找最后一行的最小即可

import java.util.List;

public class Main2 {
    public int minimumTotal(List<List<Integer>> triangle) {
        int min = Integer.MAX_VALUE;  // 定义最小值，方便后续作比较
        int row = triangle.size(); // 行数

        // 定义二维数组，用于存储每个位置的最小路径和
        int[][] f = new int[row][row];
        // 初始化第一行：
        f[0][0] = triangle.get(0).get(0); // 0行0列

        // 开始进行遍历
        for (int i = 1; i < row; i++) { // 注意从第1行开始，第0行已经初始化过了
            // 此时可以得到每一行集合
            List<Integer> tmp = triangle.get(i);
            // 遍历每一行的每一列
            for (int j = 0; j <= i; j++) { // 注意列数和行数的对等性
                // 分三种情况判断移动的起点
                if(j == 0) {
                    //  从最左边开始移动
                    // 注意获取该位置的元素值的方法！！：tmp.get(j)
                    // 是从原链表中获取到该位置的常量值的
                    f[i][j] = f[i-1][j] + tmp.get(j);
                } else if(i == j) {
                    // 从最右边开始移动
                    f[i][j] = f[i-1][j-1] + tmp.get(j);
                } else {
                    // 从其他中间任意位置，那就取min
                    f[i][j] = Math.min(f[i-1][j],f[i-1][j-1]) + tmp.get(j);
                }
            }
        }
        // 遍历结束后已经得到所有位置的最小路径和，此时
        // 遍历判断最后一行的min即可
        for (int i = 0; i < row; i++) {
            min = Math.min(min,f[row-1][i]);
        }

        return min;
    }
}
